1. Field of the Invention
The present invention relates to the field of data processing and data communication. More specifically, the present invention relates to the techniques for maintaining order in a pipelined process in a data processing or data communication device, where the pipelined processes may be completed out-of-order.
2. Background Information
The performance of some processes can be greatly increase by pipelining techniques in which the process simultaneously handles multiple tasks in various stages of completion. [The term xe2x80x9cprocessxe2x80x9d, as used herein, includes hardware and/or software.] FIG. 1 illustrates an example look up process that can benefit from such pipelining approaches. The example look up is of a kind that looks for matches between a presented query number 102 and a threaded list of entries 104. Each entry 106 consists of comparand 108, payload 110 and pointer 112. Each pointer 112 points to the location of the next entry, except for the last entry 106, whose xe2x80x9cpointerxe2x80x9d 112 is set to null. The query number 102 is mapped to an initial pointer 114 that points to the beginning of the list. At each entry, the comparand 108 is matched against the query number 102. If they agree, the look up is successful, and the associated payload 110 is reported as the look up result. If they disagree, and the associated pointer 112 is non-zero, the look up process continues with the next entry 116. The process continues until either a match is found, or the last entry 106 is encountered, where the associated pointer is null (or zero). In such case, the look up process reports failure.
In practical implementations, the threaded lists are typically stored in RAM that takes several clock cycles to access. Thus, overall system performance can be improved if the look up process can be performed for multiples of these queries at the same time. The nature of the look up process, however, is such that some queries take longer to resolve than others, giving rise to the possibility that results can become available out of order.
A specific application where such situations occur is in networking switch and router applications. Network switches/routers receive continuous streams of packets, and the included IP or MAC addresses are queued and examined to determine where the packets should be switched or routed. The determination typically involves data look ups. For performance reasons, it is desirable to be able to perform the look up for multiple of these IP/MAC addresses concurrently in a pipelined multi-stage fashion. However, as alluded to earlier, by virtue of the nature of the look up, data may be found out of order for the various IP/MAC addresses.
Thus, an efficient approach to maintaining order in a pipelined process, without squandering the efficiency gained from pipelining, is desired.
The method of the present invention includes sequentially reserving a number of memory locations of a result memory for a number of processes as the processes are sequentially dispatched for execution. As an integral part of the sequential reservation, validity determination facilitators to be subsequently employed to correspondingly facilitate determining whether valid processing results of the processes have been stored into corresponding ones of the reserved memory locations are pre-determined. The method further includes sequentially reading the reserved memory locations to sequentially accept the processing results in order. Each value read from a reserved memory location is accepted only if the corresponding validity determination facilitator exhibits a predetermined relationship with a corresponding validity determination reference value. The validity determination reference values are complementarily maintained and integrally obtained through the sequential read process.